1. Field of the Invention
The present invention relates to the field of computers, and more specifically relates to structuring control transfer tables.
2. Description of the Related Art
The typical software application consists of a dynamically linked executable and several shared objects (or dynamic libraries) which are linked together at runtime to form an executable process. The main executable and shared objects that it depends on are called loadable objects or modules. Since there are usually numerous cross-module dependencies that cannot be resolved at compile time, the compiler and linker provide facilities that reduce the amount of work that needs to be done at runtime. One such facility is a control transfer table (e.g., a Procedure Linkage Table (PLT), a jump table, etc.). A control transfer table is used for execution transfers (such as function calls) from one module to another. Whenever a cross-module execution transfer request occurs in code, a compiler generates instructions to transfer execution locally to an entry in the control transfer table. The first time this entry actually gets called, the runtime linker updates it to transfer execution to the requested function in another module. Effectively, all calls to an external function go through one place, the control transfer table. Instead of updating all of these calls at runtime to refer to the external function, only the entry for the external function is updated.
While a control transfer table provides flexibility, it also induces an overhead on the cross-module function calls. Each cross-module function call goes through a control transfer code that consists of an address calculation and a jump to the called function. This code is loaded and executed, which puts additional demand on the memory hierarchy. The random nature of control transfer table generation results in a less effective memory hierarchy utilization. This overhead from the control transfer table can adversely impact the performance, especially for more cache-hungry applications. In large transaction processing applications, control transfer table related cache misses may account for more than 3% of all the instruction cache misses. Furthermore, the overhead may be even more noticeable in applications that have large control transfer tables spanning multiple memory pages. The most frequently accessed entries (i.e., the hot entries) in these tables are usually sparse, which results in heavier paging.
Modern compilers provide numerous optimizations that restructure code in an attempt to better utilize the underlying system's memory hierarchy (e.g., function and basic block ordering). However, restructuring a control transfer table goes beyond the realm of compiler optimizations, because a control transfer table is created by a linker. The compiler has little control over construction of the control transfer table by the linker.